package leetcode_题库;

import java.util.ArrayList;

/**
 * Created by IntelliJ IDEA.
 *
 * @Author : Ding
 * @create 2023/3/22 10:34
 */
public class _2_两数相加 {
    public static void main(String[] args) {
//        ListNode l1 = new ListNode(2);
//        ListNode l2 = new ListNode(5);
//        ListNode a = new ListNode(4);
//        ListNode b = new ListNode(3);
//        ListNode c = new ListNode(6);
//        ListNode d = new ListNode(4);
//
//        l1.next = a;
//        a.next = b;
//
//        l2.next = c;
//        c.next = d;

        ListNode l1 = new ListNode(9);
        ListNode l2 = new ListNode(9);
        ListNode a = new ListNode(9);
        ListNode b = new ListNode(9);
        ListNode c = new ListNode(9);
        ListNode d = new ListNode(9);
        ListNode e = new ListNode(9);
        ListNode f = new ListNode(9);
        ListNode g = new ListNode(9);
        ListNode h = new ListNode(9);
        ListNode i = new ListNode(9);

        l1.next = a;
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;
        e.next = i;

        l2.next = f;
        f.next = g;
        g.next = h;


        ListNode ret = addTwoNumbers(l1, l2);
        ArrayList<Integer> ints = new ArrayList<>();
        while (ret != null) {
            ints.add(ret.val);
            ret = ret.next;
        }
        System.out.println(ints);

    }

    /**
     * > 2023/03/22 12:01:16
     * 解答成功:
     * 	执行耗时:1 ms,击败了100.00% 的Java用户
     * 	内存消耗:41.1 MB,击败了97.27% 的Java用户
     * @param l1 原链1
     * @param l2 原链2
     * @return 新链
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //思想是建立一个新链表p，定义一个head记录头节点，然后移动操作p节点
        ListNode p = new ListNode();
        ListNode head = p;
        //定义一个进位布尔值isAdd，因为是倒序输出，所以当前位数相加大于等于10就要向下一位进位（因为是倒序）
        boolean isAdd = false;
        //当l1和l2任何一个链表不为空，循环都继续
        while (l1 != null || l2 != null) {
            //计算p节点处的值，因为两原链有可能有一条为空，所以作一个三元判断，最后代表如果上一位相加有进位发生，则此位+1（两个位相加必然不会超过18，所以进位数必然是1）
            p.val = (l1 != null ? l1.val : 0) + (l2 != null ? l2.val : 0) + (isAdd ? 1 : 0);
            //如果当前节点p处的值达到10以上，则取个位，并且记录进位，否则记录非进位
            if (p.val / 10 > 0) {
                p.val = p.val % 10;
                isAdd = true;
            } else {
                isAdd = false;
            }
            //如果l1处不为null，则next
            if (l1 != null){
                l1 = l1.next;
            }
            //如果l2处不为null，则next
            if (l2 != null){
                l2 = l2.next;
            }
            //最后，如果两原链有一个不为null，都给p节点new一个next节点
            //看似判断冗余，其实不然，如果最后一位（正序的最高位）相加后不进位，不加判断最后一定会多一个值0。
            if(l1 != null || l2 != null){
                p.next = new ListNode();
                p = p.next;
            }
        }
        //最后，如果最后一位（正序的最高位）相加后进位，则需要开辟一个新的节点放在后面，记录值1
        if (isAdd){
            p.next = new ListNode(1);
        }
        //p节点作为指针已经走远，选择指向头节点的head指针返回
        return head;
    }

}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}